본문으로 건너뛰기

92343 - 양과 늑대

정보
  • 문제 보기: 92343 - 양과 늑대
  • 소요 시간: 💥1시간 초과
  • 풀이 언어: java
  • 체감 난이도: 3️⃣~4️⃣ (3.8)
  • 리뷰 횟수: ✅

풀이 키워드​

스포주의

백트래킹 비트마스킹


풀이 코드​

정보
  • 메모리: 90500 KB
  • 시간: 3 ms
import java.util.*;

class Solution {
    List<Integer> ansList;
    int[][] _edges;
    int[] _info;
    boolean[] visited;
    
    public void dfs(int sheep, int wolf) {
        if (sheep > wolf) ansList.add(sheep);
        else return; // base case
        
        for (int[] e : _edges) {
            if (visited[e[0]] && !visited[e[1]]) {
                visited[e[1]] = true;
                if (_info[e[1]] == 0) dfs(sheep+1, wolf); // 가려는 곳이 양
                else dfs(sheep, wolf+1); // 가려는 곳이 늑대
                visited[e[1]] = false;
            }
        }
    }
    
    public int solution(int[] info, int[][] edges) {
        _edges = edges;
        _info = info;
        ansList = new ArrayList<>();
        visited = new boolean[info.length];
        Arrays.fill(visited, false);
        visited[0] = true;
        dfs(1, 0);
        
        return Collections.max(ansList);
    }
}

풀이 해설​

상태공간 트리를 dfs로 탐색하는 백트래킹 문제이다. (물론 bfs도 가능한데, dfs가 편함.)

각 간선 e = (s, t)를 순회하며 방문한 정점 s로부터 방문하지 않은 정점 t로 재귀 호출하여 경우의 수를 탐색한다.

다시 말해, 현재 방문한 정점들로 구성되는 그래프로부터, 점점 영역 확장을 시도하는 것이다.


📌 정답 후보 구하기​

각 방문 상태 별로 유효한(promising) 경우의 수이면 해당 경우의 양 마리 수를 후보군에 올린다.

📌 가지치기하기 (pruning)​

늑대가 양의 수보다 같거나 크면 갖다 버리는(non-promising) 경우의 수이므로 가지치기 해준다.

이렇게 가지치기하여 non-promising한 노드가 제거된 부분트리를 pruned state space tree라고 한다.

if (sheep > wolf) ansList.add(sheep); // candidate
else return; // base case

주의

❌ 공식 풀이에 오류가 있음​

프로그래머스도 틀왜맞 처리해줌. 유구한 전통

갓킹독에 의하면 백트래킹도 TLE 터지는 알고리즘이라 통과되면 안된다고 한다.

생각해보니 visited 처리를 정점 기준으로 하고 있는데, 이러면 서로 다른 경로로 같은 state에 도달할 가능성이 있다.

예를 들어 state가 다음과 같다고 하자.

  a
 / \
b   c

해당 state는 a - b 라는 state에서 c를 방문하여 도달할 수도 있고

a - c 라는 state에서 b를 방문하여 도달할 수도 있다.

결국 중복 state 연산으로 비효율성이 발생하기에 엄연히는 정점이 아니라 각 state를 visited 처리해주어야 한다.

이 경우 n=17n = 17 이라 가능한 state는 2172^{17} 개이며, 비트마스킹 처리해주면 된다.

비트마스킹 예시
boolean[] visited = new boolean[1<<17]; // visited[x]: 상태 x를 방문했는가?
...
void dfs(int state) {
    if(visited[state]) return; // 이미 방문함
    ...
    // 다음 상태 탐색 (현재 정점 = i)
    for (int i = 0; i < n; ++i) {
        // i번째 비트가 꺼져있는 경우 정점 i를 방문한게 아니므로 패스
        if((state & (1<<i)) == 0) continue;
        // 왼쪽 자식이 있다면
        if(l[i] != -1)
            dfs(state | (1<<l[i]));
        // 오른쪽 자식이 있다면
        if(r[i] != -1)
            dfs(state | (1<<r[i]));
    }
}

메모​

  • 다시 풀어볼 가치가 있는 문제이다.
  • 유형에 익숙하면 3 난이도 맞고 안익숙하면 3.5, 최적화까지 포함하면 현재 체감 난이도 3.8.
  • 어쩐지 n이 작아서 뭔가 싶었는데 이진 트리 상의 탐색이 아니었다.
    • 그림은 함정ㅋ임
    • n이 작으면 일단 완탐 의심 -> 그 기반의 +a 최적화 기법 떠올리기
  • 오래 매달려서 이진 트리 상의 dfs/bfs로 풀 수 있는 패턴을 찾으려 했는데 안찾아지더라...
    • 실전에서 패턴 잘 안보이면 상태 트리로 바꾸어 생각해볼 것